package com.jn.algorithm.day005.question17;

import java.util.*;

/**
 * @author 江南大学1033190417
 * @date 2022/4/19 17:00
 */
public class Solution {

    Map<Character, String> phoneMap = new HashMap<Character, String>() {{
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};

    //宽度优先搜索
    public List<String> letterCombinations2(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Queue<String> queue = new LinkedList<>();
        String s = phoneMap.get(digits.charAt(0));
        for (int i = 0; i < s.length(); i++) {//先把第一个入队
            queue.add(String.valueOf(s.charAt(i)));
        }
        for (int i = 1; i < digits.length(); i++) {
            String str = phoneMap.get(digits.charAt(i));
            List<String> list = new ArrayList<>();
            while (!queue.isEmpty()) {
                String poll = queue.poll();
                for (int j = 0; j < str.length(); j++) {
                    list.add(poll + str.charAt(j));
                }
            }
            queue.addAll(list);
        }
        combinations.addAll(queue);
        return combinations;
    }


    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        backtrack(combinations, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "23";
        System.out.println(solution.letterCombinations(s));
    }

}
